package com.dyz.baseAlgorithm.sortingAlgorithm;

/**
 * @author: daiyizheng
 * @date: 2021/5/9 20:12
 * @description:
 */
public class QuickSort {
    public static void main(String[] args) {
        int [] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        int left = 0;
        int right = arr.length-1;

        quickSort(arr, left, right);
        for (int j : arr) {
            System.out.print(j + "\t");
        }
    }

    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex>=rightIndex){
            return ;
        }

        int left = leftIndex;
        int right = rightIndex;

        //待排序的第一个元素作为基准值
        int key = arr[left];

        //从左右两边交替扫描，直到left == right
        while (left<right){
            //从右往左扫描，找到第一个比基准值小的元素
            while (left< right && arr[right] >=key){
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) {
                //从左往右扫描，找到第一个比基准值大的元素
                left++;
            }
            //找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];

            //基准值归位
            arr[left] = key;
            //对基准值左边的元素进行递归排序
            quickSort(arr, leftIndex, left - 1);
            //对基准值右边的元素进行递归排序。
            quickSort(arr, left + 1, rightIndex);
        }

    }
}
